\documentclass[11pt,a4paper,final,notitlepage]{article}
%\usepackage[latin1]{inputenc}
\usepackage{times}

\setlength{\hoffset}{0pt}  	
\setlength{\oddsidemargin}{0pt} 	% Marge gauche sur pages impaires
\setlength{\evensidemargin}{0pt} 	% Marge gauche sur pages paires
\setlength{\marginparwidth}{35pt} 	% Largeur de note dans la marge
\setlength{\textwidth}{450pt} 	% Largeur de la zone de texte (17cm)
\setlength{\marginparsep}{0pt} 	% Sparation de la marge
\setlength{\voffset}{0pt} 	% Bon pour DOS
\setlength{\topmargin}{0pt} 	% Pas de marge en haut
\setlength{\headheight}{0pt} 	% Haut de page
\setlength{\headsep}{0pt} 	% Entre le haut de page et le texte
\setlength{\footskip}{10pt} 	% Bas de page + sparation
\setlength{\textheight}{700pt} 	% Hauteur de la zone de texte (25cm) 
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{makeidx}
\usepackage{listings}
\usepackage{graphicx}

\begin{document}
\thispagestyle{empty}
\pagestyle{empty}

\section*{Advanced Algorithms -- Homework Set 1}

\begin{tabbing}
\textbf{Authors:} \=Valentina Sintsova (\texttt{valentina.sintsova@epfl.ch}), 
			\\ \> Javier Picorel (\texttt{javier.picorel@epfl.ch}),
			\\ \> Vasileios Trigonakis (\texttt{vasileios.trigonakis@epfl.ch})\=
\end{tabbing}
\vspace*{10pt}
\paragraph*{Question 1.} Using any of your favorite solution methods, solve the following recurrences in $\Theta$ terms.

\subparagraph*{4.} a bit harder: let $f(n) = f(n - 1)/2 + 2/f(n - 1)$, with $f(0) = 3$, and define $g(n) = \prod_{i = 1}^{n}f(i)$ (hint: guess what the answer may be and verify it using limits of ratios)
\\\\
%solution
We first calculate some values for function $f$:
\\\\
$f(0) = 3$\\\\
$f(1) = \dfrac{3}{2} + \dfrac{2}{3} = \dfrac{2^{2} + 3^{2}}{2 * 3} = 13/6$\\\\
$f(2) = \dfrac{13}{12} + \dfrac{12}{13} = \dfrac{12^{2} + 13^{2}}{12 * 13} = 313/156$\\\\
$f(3) = \dfrac{313}{312} + \dfrac{312}{313} = \dfrac{312^{2} + 313^{2}}{312 * 313}$\\\\
$\cdots$
\\\\
We recognize that the divisors $(2*3, 12*13, 312*313, ...)$ are produced by the following recurrence: $c(n) = 2c(n-1)(2c(n-1) + 1)$, with $c(0) = 1$. Replacing on $f(n)$ we get:\\
\\\\
$f(n) = \dfrac{(2c(n-1) + 1)^{2} + (2c(n-1))^{2}}{2c(n-1)(2c(n-1) + 1)} = 
 \dfrac{4 (c(n-1))^2 + 4 c(n-1) + 1 + 4(c(n-1))^{2}}{2c(n-1)(2c(n-1) + 1)}=\\\\\\
= \dfrac{4c(n-1)(2c(n-1) + 1) + 1}{2c(n-1)(2c(n-1) + 1)}
=  2 + \dfrac{1}{2c(n-1)(2c(n-1) + 1)} = $ \fbox{$2 + \dfrac{1}{c(n)}$}
\\\\\\
so $f(n)$ is clearly $\Omega(2)$. Moreover, since $c(n)$ is a genuinely ascending sequence $f(n)$ is $O(2)$ and therefore $f(n)$ is $\Theta(2)$.
\\\\
Now, having $g(n) = \prod_{i = 1}^{n}f(i)$ we get:\\\\
$g(n) = f(1)f(2) \ldots f(n-2)f(n-1) = (2 + \dfrac{1}{c(1)})(2 + \dfrac{1}{c(2)}) \ldots (2 + \dfrac{1}{c(n-2)})(2 + \dfrac{1}{c(n-1)}) =\\\\
2^{n} + 2^{n-1} (\dfrac{1}{c(1)} + ... + \dfrac{1}{c(n)}) + 2^{n-2} (\dfrac{1}{c(1)*c(2)} + \ldots) + 2^{n-3} (\ldots) + \ldots + \dfrac{1}{c(1)* \ldots *c(n)}
$\\\\
and since $\forall n \ge 0, c(n) > 1$, we have that $g(n)$ is $\Theta(2^{n})$ if the term $2^{n}$ is the ``strongest'' in the addition.

To prove it we prove that $\dfrac{1}{c(1)} + ... + \dfrac{1}{c(n)} = \sum_{i = 1}^{n}\dfrac{1}{c(i)} \le 1$, which will imply that any other sum in the form $\sum_{1\le i_1,..,i_k\le n}\dfrac{1}{c(i_1)c(i_2)\dots c(i_k)} = \sum_{1\le i_1,..,i_{k-1}\le n}\dfrac{1}{c(i_1)c(i_2)\dots c(i_{k-1})} \sum_{ i_k =1}^{ n} \dfrac{1}{c(i_k)} \le\\\\ \le  \sum_{1\le i_1,..,i_{k-1}\le n}\dfrac{1}{c(i_1)c(i_2)\dots c(i_{k-1})}\le \dots \le 1$
\\\\\\
We will first show that $c(n) > 2^{n}$:\\\\\\
$c(n) = 2c(n-1)(2(c(n-1) + 1) > 2^{2} c^{2}(n-1) > 2^{4} c^{2}(n-2) > \ldots > 2^{2n} c^{2}(0) = 2^{2n} > 2^n$ \\\\
so $\dfrac{1}{c(n)} < \dfrac{1}{2^{n}} \Rightarrow \sum_{i = 1}^{n} \dfrac{1}{c(i)} < \sum_{i = 1}^{n} \dfrac{1}{2^{i}}$
\\\\\\but $\sum_{i = 1}^{n} \dfrac{1}{2^{i}} = \dfrac{2^{n} - 1}{2^{n}} < 1$ \textbf{Q.E.D.}

\paragraph*{Question 5.} Matrix multiplication is easy to break into subproblems. For example, if we are given $A = 
\begin{vmatrix}
A_{11} & A_{12}\\
A_{21} & A_{22}
\end{vmatrix}
$
and $B = 
\begin{vmatrix}
B_{11} & B_{12}\\
B_{21} & B_{22}
\end{vmatrix}
$
\\then we can compute the product $AB$ as follows:
\\$AB =
\begin{vmatrix}
A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \\
A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22}
\end{vmatrix}$\\
(A and B are ($n \times n$) matrices, and Aij and Bi,j are ($n/2 \times n/2$) matrices.) Now use this divide-and-conquer approach recursively until each block has one element. Analyze the resulting number of multiplications.
\\\\\\
If $n$ is the number of elements of each matrix\footnote{for matrix $A[1..m, 1..m], n = m \times m$}, then we get the following recurrence describing the number of multiplications:
\begin{equation}
T(n) = 8T(n/4)
\end{equation}
since each multiplication is broken of 8 matrix multiplications with input the $1/4$ of the initial size.
\\This recurrence can be solved using the master theorem which gives that $T(n)$ is $\Theta(n^{\log _{4} 8}) = \Theta(n^{3/2})$
\end{document}